The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) or link state advertisement (LSA) dependent on the protocol each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” (SPT) is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node the node identifies the optimum route to that destination and forwards the packet via the corresponding interface to the next node (“NEXT_HOP”) along that route. The next node repeats this step and so forth.
It will be noted that in normal forwarding each node decides, irrespective of the node from which it received a packet, the next node to which the packet should be forwarded. In some instances this can give rise to a “loop”. In particular this can occur when the databases (and corresponding forwarding information) are temporarily de-synchronized during a routing transaction, that is, where because of a change in the network, a new LSP is propagated that induces creating a loop in the RIB or FIB. As an example, if a node A sends a packet to a node Z via a node B, comprising the optimum route according to its SPF, a situation can arise where node B, according to its SPF determines that the best route to node Z is via node A and sends the packet back. This can continue for as long as the loop remains although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes.
One solution that has been proposed to the looping problem is described in co-patent pending patent application Ser. No. 11/064,275 filed 22 Feb. 2005, entitled “Method and Apparatus for Constructing a Repair Path around a Non-Available Component in a Data Communications Network” of Michael Shand et al (“Shand et al”), the entire contents of which is incorporated by reference for all purposes as if fully set forth herein and as discussed in more detail below.
According to the repair scheme described in Shand et al, in addition to the standard IP addresses assigned to each router or node in a network, each interface is assigned an additional repair address termed, in Shand et al, the “notvia address”. The semantics of a notvia address are that a packet addressed to a not via address must be delivered to the router with that address, not via the neighbouring router on the interface to which that address is assigned. All nodes in the network then calculate their next hop not only for each normal address but also for each notvia address. As a result, when a neighbour node to a component (link or node) identifies that the component has failed it tunnels packets which it would have otherwise sent to the failed component to the appropriate notvia address on the other side of the failure. As all other nodes have pre-calculated their own next hop for that notvia address then the tunneled packed will be forwarded correctly and decapsulated on arrival at the notvia address from where it is forwarded as normal. Accordingly, looping does not occur.
In order to optimise the method in Shand et al the computational burden of an additional SPF calculation for each notvia address is reduced by using incremental SPFs (ISPF). The ISPF approach is described in co-pending patent application Ser. No. 09/687,009, filed 12 Oct. 2000, entitled “Method and System for Accelerating Route Calculation in Link State Routing Protocols” of John Harper (“Harper”), the entire contents of which are incorporated by reference for all purposes as if fully set forth herein. ISPF recognizes that following a topology change, only the affected part of the SPT requires recomputation. Accordingly it is simply necessary to prune the affected component (whether node or link), identify which components have been detached from the SPT as a result and reattach those components. In a further optimization discussed in Shand et al the ISPF calculation is terminated when all notvia addresses have been reattached.
However the approach described in Shand et al still requires a significant amount of ISPF computation. A further optimization described in Shand et al can be understood with reference to FIG. 1 which depicts an illustrative network diagram of a network topology to which the optimization can be applied. A network generally referenced 100 included nodes A, B, C, D, E, F, X, Y, Z, reference numerals 102, 104, 106, 108, 110, 112, 114, 116, 118 respectively. Node B is joined to nodes A, C, D, E, via respective links 120, 122, 124, 126. Node C provides a route 128 to node F which may be a single or multiple hops. Node A is connected to node X via a route 130 which may also be single or multiple hops. Each node advertises, in addition to its normal address, a notvia address for each respective interface. For example as shown in FIG. 1, node b advertises notvia addresses BĀ, BC, BD, BĒ, in relation to its interfaces with respective nodes A, C, D, E. In addition it can be seen, for example, that nodes A, C, D and E advertise notvia addresses AB, CB, DB, EB respectively.
According to normal notvia configuration as described in Shand et al, in relation to, for example, notvia address BĀ, advertised by node B, each other node in the network calculates its route to that notvia address. Then, if the link to the corresponding interface, connecting to node A, fails, packets arriving at node A with next hop node B are tunneled by node A to notvia address BĀ. As shown in FIG. 1, where link AB reference numeral 120, has failed, A tunnels packets along a notvia route designated generally 132 via nodes Y and Z to node B. Node B then decapsulates the tunneled packets which are then forwarded normally.
Accordingly it will be seen that in fact only the nodes Y and Z, i.e. those in the notvia repair path 132 in fact use the notvia address even though all nodes in the network have calculated their next hop for BĀ. According to an optimization proposed in Shand et al, only the nodes on the notvia repair path calculate their notvia addresses however this requires signaling to those nodes.